// ml:run = time -p $bin < input
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <cmath>

int const maxn = 100007;

int clog2[maxn];

template <class T>
void scan(T & a)
{
	a = 0;
	bool flag = false;
	char ch = std::getchar();
	if (ch == '-')
		flag = true;
	else if (ch >= '0' && ch <= '9')
		a = ch - '0';

	while ((ch = std::getchar()) >= '0' && ch <= '9')
		a = a * 10 + ch - '0';
	if (flag) a = -a;
}

template <
	class T,
	class COMPARE = std::less<T>
>
struct sparse_table
{
	typedef T value_type;
	typedef unsigned int size_type;
	typedef COMPARE comparer;
	typedef std::vector<value_type> vector_type;

	inline size_type log2(size_type len) const
	{
		/* return std::log(len)/log(2); */
        return clog2[len];
	}

	sparse_table(vector_type const & data, comparer cmp = comparer())
		: data(data), cmp(cmp)
	{
		size_type n = data.size();
		size_type len = log2(n);
		st.resize(n);
		for (typename std::vector<vector_type>::iterator it = st.begin();
				it != st.end(); ++it)
			(*it).resize(len + 1);

		for (size_type i = 0; i < n; i++) st[i][0] = i;
		for (size_type l = 1; l <= len; l++)
			for (size_type i = 0; (i + (1<<l) - 1) < n; i++)
				if (cmp(data[ st[i + (1<<(l-1))][l - 1] ], data[ st[i][l - 1] ]))
					st[i][l] = st[i + (1 << (l-1))][l - 1];
				else
					st[i][l] = st[i][l - 1];
	}

	// [l, r]
	size_type query_interval_index(size_type l, size_type r) const
	{
		int k = log2(r - l + 1);
		if (cmp(data[ st[r - (1<<k) + 1][k] ], data[ st[l][k] ]))
			return st[r - (1<<k) + 1][k];
		else
			return st[l][k];
	}

	// [l, r]
	value_type query_interval(size_type l, size_type r) const
	{
		return data[ query_interval_index(l, r) ];
	}

private:
	std::vector<vector_type> st; // store the index of the dest value
	vector_type const & data;
	comparer cmp;
};

int n, q;
std::vector<int> v;

void init()
{
    for (int i = 0; i < maxn; i++) {
		int tmp = 0;
		for (; (1 << tmp) <= i; ) tmp++;
        clog2[i] = tmp - 1;
    }
}

int main()
{
    /* std::ios_base::sync_with_stdio(false); */
    int T; scan(T);
    init();
    /* std::cin >> T; */
    while (T--) {
        /* std::cin >> n; */
        scan(n);
        v.resize(n);
        for (int i = 0; i < n; i++) scan(v[i]);
            /* std::cin >> v[i]; */
        sparse_table<int> st(v);
        /* std::cout << st.query_interval_index(0, n - 1) << "\n"; */
        /* std::cin >> q; */
        scan(q);
        for (int i = 0; i < q; i++) {
            int l, r; scan(l); scan(r);
            /* std::cin >> l >> r; */
            l--; r--;
            int ans = v[l]; l++;
            while (l <= r) {
                int tl = l, tr = r;
                while (tl + 1 < tr) {
                    int mid = (tl + tr) / 2;
                    if (st.query_interval(mid, r) > ans) tl = mid;
                    else tr = mid;
                    /* std::cerr << ":: " << mid << "\n"; */
                }
                if (st.query_interval(tl, r) <= ans) tr = tl;
                if (st.query_interval(tr, r) > ans) break;
                if (tr > r) break;
                ans %= v[st.query_interval_index(tr, r)];
                l = st.query_interval_index(tr, r) + 1;
                /* std::cerr << ":: " << tr << "\n"; */
            }
            printf("%d\n", ans);
            /* std::cout << ans << "\n"; */
        }
    }
}

